package com.openess.bigsearch.engine.utils;

import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

import com.openess.bigsearch.engine.BTree.util.CCollection;

/**
 * 链表最大的优势在于方便进行插入，删除操作。包含头指针以及尾指针，支持头/尾O(1)插入/删除，同时有头节点(不含任何数据)，头尾插入统一。
 * 
 * @author TuTu
 */
public class LinkedList<E> implements List<E> {
	/**
	 * 头指针，并非头节点
	 */
	protected Node<E> head;
	/**
	 * 尾指针，方便未插入和尾删除
	 */
	private Node<E> rear;
	/**
	 * 链表中的实际Node数
	 */
	private int size;

	/**
	 * 默认构造器，没有传入任何值，因此构造出的链表为空，头尾指针都指向头节点Node<E>(null)，头节点永远不含数据
	 */
	public LinkedList() {
		this.head = new Node<E>(null);
		this.rear = this.head;
		this.size = 0;
	}

	/**
	 * 构造方法，先构造一个空链表再插入一个值
	 * 
	 * @param data
	 */
	public LinkedList(E data) {
		this();
		addFirst(data);
	}

	public boolean addFirst(E element) {
		if (element != null) {
			Node<E> p = new Node<E>(element, this.head.getNext());
			this.head.setNext(p);
			// 如果头插入的时候，链表只有一个头节点，那么还需要移动尾指针
			if (this.size == 0) {
				this.rear = p;
			}
			this.size++;
			return true;
		}
		return false;
	}

	@Override
	public boolean add(E element) {
		if (element != null) {
			Node<E> p = new Node<E>(element, null);
			this.rear.setNext(p);
			this.rear = p;
			this.size++;
		}
		return false;
	}

	@Override
	public void add(int index, E element) {
		if (index >= 0 && element != null) {
			// 尾插入,单独判断提高效率
			if (index >= this.size) {
				add(element);
			} else {
				int i = 0;
				Node<E> p = this.head;
				while (p.getNext() != null && i < index) {
					p = p.getNext();
					i++;
				}
				p.setNext(new Node<E>(element, p.getNext()));
				this.size++;
			}
		}
	}

	@SuppressWarnings("unchecked")
	@Override
	public boolean addAll(Collection<? extends E> c) {
		if (c == null) {
			return false;
		}
		Object[] a = (Object[]) c.toArray();
		for (int i = 0; i < a.length; i++) {
			add((E) a[i]);
		}
		return true;
	}

	@Override
	public void clear() {
		this.head = new Node<E>(null);
		this.rear = this.head;
	}

	@Override
	public E get(int index) {
		int i = 0;
		if (this.head != null && index >= 0) {
			Node<E> p = this.head.getNext();
			while (p != null && i < index) {
				p = p.getNext();
				i++;
			}
			if (p != null) {
				return p.getData();
			}
		}
		return null;
	}

	@Override
	public boolean isEmpty() {
		return this.head.getNext() == null;
	}

	@Override
	public E remove(int index) {
		E old = null;
		if (!isEmpty() && index >= 0) {
			int i = 0;
			Node<E> p = this.head;
			while (p.getNext() != null && i < index) {
				p = p.getNext();
				i++;
			}
			if (p.getNext() != null) {
				old = p.getNext().getData();
				p.setNext(p.getNext().getNext());
				this.size--;
			}
		}
		return old;
	}

	@Override
	public E set(int index, E element) {
		int i = 0;
		E old = null;
		if (!isEmpty() && index >= 0 && element != null) {
			Node<E> p = this.head.getNext();
			while (p != null && i < index) {
				p = p.getNext();
				i++;
			}
			if (p != null) {
				old = p.getData();
				p.setData(element);
			}
		}
		return old;
	}

	@Override
	public String toString() {
		String str = "";
		if (head != null) {
			Node<E> p = this.head.getNext();
			str = p.getData().toString();
			while (p.getNext() != null) {
				p = p.getNext();
				str = str + "--" + p.getData().toString();
			}
		}
		return str;
	}

	@Override
	public java.util.Iterator<E> iterator() {
		return new Itr();
	}

	@Override
	public Object[] toArray() {
		Object[] result = new Object[size];
		Node<E> p = this.head.getNext();
		for (int i = 0; p != null; i++) {
			result[i] = p.getData();
			p = p.getNext();
		}
		return result;
	}

	@SuppressWarnings("unchecked")
	@Override
	public <T> T[] toArray(T[] a) {
		// 如果a数组装不下，那么创建一个泛型数组
		if (a.length < size) {
			a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
		}
		// 将数组a的引用传给变量result，result的改动也会造成数组a的变动，此处必须这么写，因为无法直接把值放入a中，因为两者的泛型类型不同
		Object[] result = a;
		Node<E> p = this.head.getNext();
		for (int i = 0; p != null; i++) {
			result[i] = p.getData();
			p = p.getNext();
		}
		return a;
	}

	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T a) {
		T[] array = (T[]) Array.newInstance(a.getClass(), size);
		// 将数组a的引用传给变量result，result的改动也会造成数组a的变动，
		// 此处必须这么写，因为无法直接把值放入a中，因为两者的泛型类型不同
		Object[] result = array;
		Node<E> p = this.head.getNext();
		for (int i = 0; p != null; i++) {
			result[i] = p.getData();
			p = p.getNext();
		}
		return array;
	}

	/**
	 * 链表的遍历实现，Itr不能加泛型，否则会造成内部类中的E无法与外部类中的E进行匹配，被认为不是一个类型
	 * 
	 * @author TuTu
	 * 
	 */
	private class Itr implements Iterator<E> {
		/**
		 * 用于记录当前迭代器遍历到哪个节点了
		 */
		private Node<E> p;

		/**
		 * 内部类的构造方法，初始化拿到头节点
		 */
		public Itr() {
			this.p = LinkedList.this.head.getNext();
		}

		@Override
		public boolean hasNext() {
			return p != null;
		}

		@Override
		public E next() {
			E data = p.getData();
			p = p.getNext();
			return data;
		}

		@Override
		public void remove() {
		}

	}

	@Override
	public int size() {
		return this.size;
	}

	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int indexOf(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public int lastIndexOf(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public ListIterator<E> listIterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public ListIterator<E> listIterator(int index) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		// TODO Auto-generated method stub
		return null;
	}
}
